|
In computer science, Thompson's construction is an algorithm for transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression. Regular expression and nondeterministic finite automaton are two abstract representation of formal languages. While regular expressions are used e.g. to describe advanced search patterns in "find and replace"-like operations of text processing utilities, the NFA format is better suited for execution on a computer. Hence, this algorithm is of practical interest, since it can be considered as a compiler from regular expression to NFA. On a more theoretical point of view, this algorithm is a part of the proof that they both accept exactly the same languages, that is, the regular languages. A thus obtained automaton can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression, but it may also be used directly. == The algorithm == The algorithm works recursively by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules. More precisely, from a regular expression , the obtained automaton with the transition function respects the following properties: * has exactly one initial state , which is not accessible from any other state. That is, for any state and any letter , does not contain . * has exactly one final state , which is not co-accessible from any other state. That is, for any letter , . * Let be the number of concatenation of the regular expression and let be the number of symbols apart from parentheses — that is, , , and . Then, the number of states of is (linear in the size of ). * The number of transitions leaving any state is at most two. * Since an NFA of states and at most transitions from each state can match a string of length in time , a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.〔(【引用サイトリンク】last=Xing )〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Thompson's construction」の詳細全文を読む スポンサード リンク
|